package code1.dp;

/**
 * 原题链接：https://leetcode.cn/problems/combination-sum-iv/
 */
public class P377 {

    //用nums数组里的数组成target目标值有多少种方法,每个数可用多次
    //完全背包问题,能装多少种的问题，dp[j]表示组成j有多少种组法
    public int combinationSum4(int[] nums, int target) {
        int[] dp=new int[target+1];
        dp[0]=1;
        for(int i=1;i<=target;i++){         //求排列,先遍历背包容量，再遍历物品
            for(int j=0;j<nums.length;j++){
                if(i-nums[j]>=0){
                    dp[i]+=dp[i-nums[j]];
                }
            }
        }
        return dp[target];
    }
}
